
#pragma once

#include "atr/containers/modifiers/pop.hpp"
#include "atr/containers/modifiers/push.hpp"
#include "atr/containers/operations/merge.hpp"

namespace atr {

/**
 * @brief Namespace only for internal use of atr library
 * @details Please don't use this namespace outside the atr library. IF you REALLY need to - do it with special care.
 */
namespace __ {

template <class Left, class Right,
          template <class, class> class Comparator,
          bool isSplited>
    struct __sort;

template <template <class ...> class Base,
          template <class, class> class Comparator>
struct __sort<Base<>, Base<>,
              Comparator,
              true>
{
    using type = Base<>;
};

template <template <class ...> class Base,
          class Left,
          template <class, class> class Comparator>
struct __sort<Base<Left>, Base<>,
              Comparator,
              true>
{
    using type = Base<Left>;
};

template <template <class ...> class Base,
          class Right,
          template <class, class> class Comparator>
struct __sort<Base<>, Base<Right>,
              Comparator,
              true>
{
    using type = Base<Right>;
};

template <template <class ...> class Base,
          class ... Lefts, class Right, class ... Rights,
          template <class, class> class Comparator>
struct __sort<Base<Lefts...>,
              Base<Right, Rights...>,
              Comparator,
              false>
    : public __sort<Base<Lefts..., Right>,
                    Base<Rights...>,
                    Comparator,
                    ((sizeof ... (Lefts) +1) >= (sizeof ... (Rights)))> {};

template <template <class ...> class Base,
          class ... Lefts, class ... Rights,
          template <class, class> class Comparator>
struct __sort<Base<Lefts...>,
              Base<Rights...>,
              Comparator,
              true>
{
    // TODO: refactor
    // \ looks creepy, but is quite flexible
    using type = typename
                 __pop<Base<>,
                       typename
                       __merge<Base<>,
                               typename
                               __push<typename
                                      __sort<Base<>,
                                             Base<Lefts...>,
                                             Comparator,
                                             sizeof ... (Lefts) == 0>::type
                                      >::template push_front<bool>,
                               typename
                               __sort<Base<>,
                                      Base<Rights...>,
                                      Comparator,
                                      sizeof ... (Rights) == 0>::type,
                               Comparator,
                               true
                               >::type
                       >::pop_front;
};

} // namespace __
} // namespace atr